#include<stdio.h>
#include<string.h>
// 归并排序非递归实现
void _merge(int *a,int *s,int left, int mid,int right) { //8,9,9
    int x = left; //8
    int b = left; //8
    int c = mid;  //9
    while ((b < mid) && (c <= right)) {
        if (a[b] >= a[c]) {
            s[x] = a[c];
            c++;
        }
        else {
            s[x] = a[b];
            b++;
        }
        x++;
    }
    while (b < mid) {
        s[x++] = a[b++];
    }
    while (c <= right) {
        s[x++] = a[c++];
    }
}
void MergeSortNonR(int* a, int n) {
    int i = 1;
    int j = 0;
    int t[100];
    int mid = 0;
    for (i = 2; i < 2 * n; i*=2) { 
        for (j = 0; j < n ; j += i) { //n=10
            if (j + i > n + 1) {
                if (j != 0) {
                    mid = (j + n) / 2 - 1;
                }
                else {
                    mid = i / 2;
                }
                _merge(a, t, j, mid  , n - 1 );
                memcpy(a + j, t + j, sizeof(int) * ( n - j));
            }
            else {
                mid = (j + j + i - 1) / 2;
                _merge(a, t, j, mid + 1 , j + i - 1);
                memcpy(a + j, t + j, sizeof(int) * i);
            }
        }
    }
}
int main() {
     int array[] = { 1,3,5,7,9,2,4,6,8,0};
     int n = sizeof(array) / sizeof(array[0]);
     //MergeSort(array, array, 0, n-1);
     MergeSortNonR(array, n );
     int i = 0;
     for (i = 0; i < n; i++) {
           printf("%d ", array[i]);
     }
     printf("\n");
     return 0;
}

